#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 比较两个数组元素大小
int comp(int a, int b) { return a - b; }

// 交换数组元素
void swap(vector<int>& a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

// 冒泡排序
void bubbleSort(vector<int>& a) {
    int bound, exchange = a.size() - 1;
    while (exchange != 0) {
        bound = exchange;
        exchange = 0;
        for (int i = 0; i < bound; i++) {
            if (comp(a[i], a[i + 1]) > 0) {
                swap(a, i, i + 1);
                exchange = i;
            }
        }
    }
}

// 选择排序
void selectSort(vector<int>& a) {
    for (int i = 0; i < a.size() - 1; i++) {
        int index = i;
        for (int j = i + 1; j < a.size(); j++) {
            if (comp(a[j], a[index]) < 0)
                index = j;
        }
        if (index != i)
            swap(a, i, index);
    }
}

// 插入排序
void insertSort(vector<int>& a) {
    for (int i = 1; i < a.size(); i++) {
        int t = a[i], j = i - 1;
        for (; j >= 0 && t < a[j]; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = t;
    }
}

// 归并排序
vector<int> mergeSort(vector<int>& a, int left, int right) {
    if (left > right) return {};
    if (left == right) return {a[left]};

    int mid = left + (right - left) / 2;
    vector<int> a1 = mergeSort(a, left, mid);
    vector<int> a2 = mergeSort(a, mid + 1, right);

    vector<int> c(a1.size() + a2.size());
    int i1 = 0, i2 = 0, i = 0;
    while (i1 < a1.size() && i2 < a2.size()) {
        if (a1[i1] <= a2[i2]) {
            c[i++] = a1[i1++];
        } else {
            c[i++] = a2[i2++];
        }
    }

    while (i1 < a1.size()) {
        c[i++] = a1[i1++];
    }

    while (i2 < a2.size()) {
        c[i++] = a2[i2++];
    }

    return c;
}

// 快速排序划分操作
int partition(vector<int>& a, int p, int r) {
    int pivot = a[p];
    int i = p, j = r;
    while (i < j) {
        while (i < j && pivot <= a[j])
            j--;
        if (i < j) {
            swap(a, i, j);
            i++;
        }
        while (i < j && pivot >= a[i])
            i++;
        if (i < j) {
            swap(a, i, j);
            j--;
        }
    }
    return i;
}

// 快速排序
void quickSort(vector<int>& a, int p, int r) {
    if (p < r) {
        int q = partition(a, p, r);
        quickSort(a, p, q - 1);
        quickSort(a, q + 1, r);
    }
}

// 测试排序算法
vector<int> testSort(vector<int> a) {
    int testMethod = 3;
    switch (testMethod) {
        case 1:
            bubbleSort(a);
            break;
        case 2:
            selectSort(a);
            break;
        case 3:
            insertSort(a);
            break;
        case 4:
            a = mergeSort(a, 0, a.size() - 1);
            break;
        case 5:
            quickSort(a, 0, a.size() - 1);
            break;
    }
    return a;
}

// 打印数组
static string display(const vector<int>& a) {
    string result;
    for (size_t i = 0; i < a.size(); i++) {
        result += to_string(a[i]);
        if (i < a.size() - 1) result += "\t";
    }
    return result;
}

int main() {
    vector<int> a = {49, 12, 54, 96, 26, 37, 48, 64};
    cout << "排序前：" << display(a) << endl;
    a = testSort(a);
    cout << "排序后：" << display(a) << endl;
    return 0;
}